#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <bitset>

using namespace std;

// 1219. 黄金矿工
// https://leetcode.cn/problems/path-with-maximum-gold/description/
class Solution {
    int ans;
    int n, m;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    bool check[16][16];
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i<n; ++i)
        {
            for (int j = 0; j<m; ++j)
            {
                if (grid[i][j])
                {
                    check[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    check[i][j] = false;
                }
                
            }
        }

        return ans;
    }

    void dfs(vector<vector<int>>& grid, int y, int x, int path)
    {
        for (int k = 0; k<4; ++k)
        {
            int _y = y + dy[k], _x = x + dx[k];
            if (_y>=0 && _y<n && _x>=0 && _x<m && !check[_y][_x] && grid[_y][_x])
            {
                check[_y][_x] = true;
                dfs(grid, _y, _x, path + grid[_y][_x]);
                check[_y][_x] = false;
            }
        }
        ans = max(ans, path);
    }
};

// 980. 不同路径 III
// https://leetcode.cn/problems/unique-paths-iii/
class Solution {
    int ans;
    int _step;
    int n, m;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    bool check[20][20];
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        int x = 0;
        int y = 0;
        for (int i = 0; i<n; ++i)
        {
            for (int j = 0; j<m; ++j)
            {
                if (grid[i][j] == 1)
                    y = i, x = j;
                else if (grid[i][j] == 0)
                    ++_step;
            }
        }
        check[y][x] = true;
        dfs(grid, y, x, 0);
        return ans;
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int step)
    {
        if (grid[i][j] == 2)
        {
            if (step == _step+1) ++ans;
            return;
        }

        for (int k = 0; k<4; ++k)
        {
            int y = i + dy[k], x = j + dx[k];
            if (y>=0 && y<n && x>=0 && x<m && grid[y][x]!=-1 && !check[y][x])
            {
                check[y][x] = true;
                dfs(grid, y, x, step+1);
                check[y][x] = false;
            }
        }
    }
};

// 733. 图像渲染
// https://leetcode.cn/problems/flood-fill/
class Solution {
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    int n,m;
    int nowColor;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        vector<vector<int>> ans(image);
        n = ans.size(), m = ans[0].size();
        nowColor = ans[sr][sc];
        ans[sr][sc] = color;
        dfs(ans, sr, sc, color);
        return ans;
    }

    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
    {
        for (int i = 0; i<4; ++i)
        {
            int y = sr + dy[i];
            int x = sc + dx[i];
            if (y>=0 && y<n && x>=0 && x<m && image[y][x]!=color && image[y][x]==nowColor)
            {
                image[y][x] = color;
                dfs(image, y, x, color);
            }
        }
    }
};

// 200. 岛屿数量
// https://leetcode.cn/problems/number-of-islands/
class Solution {
    int n,m;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    vector<vector<bool>> vis;
public:
    int numIslands(vector<vector<char>>& grid) {
        n = grid.size(), m = grid[0].size();
        vis = vector<vector<bool>>(n, vector<bool>(m));
        int ans = 0;

        for (int i = 0; i<n; ++i)
        {
            for (int j = 0; j<m; ++j)
            {
                if (!vis[i][j] && grid[i][j] == '1')
                {
                    ++ans;
                    dfs(grid, j, i);
                }
            }
        }

        return ans;
    }

    void dfs(vector<vector<char>>& grid, int j, int i)
    {
        vis[i][j] = true;
        for (int k = 0; k < 4; ++k)
        {
            int y = i + dy[k], x = j + dx[k];
            if (y>=0 && y<n && x>=0 && x<m && !vis[y][x] && grid[y][x]=='1')
            {
                dfs(grid, x, y);
            }
        }
    }
};

// 695. 岛屿的最大面积
// https://leetcode.cn/problems/max-area-of-island/
class Solution {
    int n, m;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    bool vis[50][50];
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i<n; ++i)
        {
            for (int j = 0; j<m; ++j)
            {
                if (!vis[i][j] && grid[i][j])
                {
                    int tmp = 0;
                    dfs(grid, i, j, tmp);
                    ans = max(ans, tmp);
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int& s)
    {
        vis[i][j] = true;
        ++s;
        for (int k = 0; k<4; ++k)
        {
            int x = j + dx[k], y = i + dy[k];
            if (x>=0 && x<m && y>=0 && y<n && !vis[y][x] && grid[y][x])
            {
                dfs(grid, y, x, s);
            }
        }
    }
};

// 130. 被围绕的区域
// https://leetcode.cn/problems/surrounded-regions/
class Solution {
    int n, m;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
public:
    void solve(vector<vector<char>>& board) {
        n = board.size(), m = board[0].size();
        for (int j = 0; j<m; ++j)
        {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[n-1][j] == 'O') dfs(board, n-1, j);
        }
        for (int i = 0; i<n; ++i)
        {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][m-1] == 'O') dfs(board, i, m-1);
        }

        for (int i = 0; i<n; ++i)
        {
            for (int j = 0; j<m; ++j)
            {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = '.';

        for (int k = 0; k<4; ++k)
        {
            int y = i + dy[k], x = j + dx[k];
            if (y>=0 && y<n && x>=0 && x<m && board[y][x]=='O')
                dfs(board, y, x);
        }
    }
};